"""
Generate plots for sorting algorithms.
"""

from time import clock
import matplotlib.pyplot as plt
import numpy.random as rnd
import sys

def merge(list2, first, last, mid):
    tempList_mr = list2[:]
    list3 = []
    list3.extend(tempList_mr[first:mid])
    list3.extend(tempList_mr[mid:last+1])
    list3.sort()
    list2[0:] = []
    list2.extend(list3)
    assert(True)
    
def swap(list2, i, j):
    tempList_s = list2[:]
    list2[i] = tempList_s[j]
    list2[j] = tempList_s[i]
    assert(True)
    
def min_element(list2, first, last):
    tempList_m = list2[:]
    compareList = tempList_m[first:last+1]
    compareList.sort()
    minItem = compareList[0]
    idx = list2.index(minItem)
    return idx
    assert(True)
    
def partition(list2, first, last, pivot):    
    tempList_p = list2[:]
    newList = tempList_p[first:last+1]
    pivotedItem = tempList_p[pivot]
    newList.sort()
    count = 0
    for num in newList:
        if num == pivotedItem:
            count = count+1
    return newList.index(pivotedItem) + count -1
    assert(True)
    
def python_builtin_sort(list2):
    list2.sort()
    
def bubble_sort(list2):
    for i in range(0, len(list2) - 1):
        sorted = True
        for j in range(0, len(list2) - i - 1):
            if list2[j] > list2[j+1]:
                swap(list2, j, j+1)
                sorted=False
            if sorted: break
            
def selection_sort(list2):
    for i in range(0, len(list2) - 1):
        swap(list2, i, min_element(list2, i + 1, len(list2)))
        
def insertion_sort(list2):
    for i in range(1, len(list2)):
        save = list2[i]
        j = i
        while j> 0 and list2[j - 1] > save:
            list2[j] = list2[j - 1]
            j -= 1
        list2[j] = save
        
def quick_sort(list2):
    quick_sort_recursive(list2, 0, len(list2) - 1)
    
def quick_sort_recursive(list2, first, last):
    if last > first:
        mid = (first + last)/2
        if list2[first] > list2[mid]: swap(list2, mid, first)
        if list2[first] > list2[last]: swap(list2, first, last)
        if list2[mid] > list2[last]: swap(list2, mid, last)
        
        pivot = partition(list2, first, last, mid)
        quick_sort_recursive(list2, first, pivot - 1)
        quick_sort_recursive(list2, pivot + 1, last)
        
def heap_sort(list2):
    first = 0
    last = len(list2) - 1
    create_heap(list2, first, last)
    for i in range(last, first, -1):
        swap(list2, i, first)
        heapify(list2, first, i - 1)
        
def create_heap(list2, first, last):
    i = last/2
    while i >= first:
        heapify(list2, i, last)
        i -= 1
        
def heapify(list2, parent, last):
    child = 2*parent + 1
    while child <= last:
        if child <= last and list2[child] < list2[child + 1]:
            child += 1
        if list2[parent] >= list2[child]:
            break
        swap(list2, parent, child)
        parent = child
        child = 2* parent + 1
        
def merge_sort(list2):
    merge_sort_recursive(list2, 0, len(list2) - 1)
    
def merge_sort_recursive(list2, first, last):
    if first < last:
        mid = (first + last)/2
        merge_sort_recursive(list2, first, mid)
        merge_sort_recursive(list2, mid + 1, last)
        merge(list2, first, last, mid)
        
def execution_time(function, *args):
    t = clock()
    function(*args)
    t = clock()-t
    return t;

def plot_times(function, sizes):
    print "timing " + function.__name__
    times = [execution_time(function, rnd.randint(1000, size=n)) for n in sizes]
    return times

def check_sorted(data):
    for i in range(len(data)-1):
        if (data[i+1] < data[i]):
            print "data[%d] and data[%d] are out of order; %d > %d."%(i,i+1, data[i], data[i+1])
    
def test_sort(function, trials=10, size=500):
    print "testing " + function.__name__
    for  k in range(trials):
        data = list(rnd.randint(1000,size=size))
        function(data)
        check_sorted(data)
        data.reverse()

        function(data)
        check_sorted(data)
     
        data = list(rnd.randint(5,size=size))
        function(data)
        check_sorted(data)
        
sys.setrecursionlimit(15000)            
test_sort(merge_sort)
test_sort(quick_sort)
test_sort(selection_sort)
test_sort(insertion_sort)
test_sort(heap_sort)
test_sort(bubble_sort)

sizes = [10, 100, 300, 600, 1000, 1500, 2000]

merge_sort_times = plot_times(merge_sort, sizes)
quick_sort_times = plot_times(quick_sort, sizes)
selection_sort_times = plot_times(selection_sort, sizes)
insertion_sort_times = plot_times(insertion_sort, sizes)
heap_sort_times = plot_times(heap_sort, sizes)
python_builtin_sort_times = plot_times(python_builtin_sort, sizes)
bubble_sort_times = plot_times(bubble_sort, sizes)


plt.plot(sizes, merge_sort_times, label="merge sort")
plt.plot(sizes, quick_sort_times, label="quick sort")
plt.plot(sizes, selection_sort_times, label="selection sort")
plt.plot(sizes, insertion_sort_times, label="insertion sort")
plt.plot(sizes, heap_sort_times, label="heap sort")
plt.plot(sizes, python_builtin_sort_times, label="python built-in sort")
plt.plot(sizes, bubble_sort_times, label="bubble sort")
plt.semilogy()
plt.title("John Femiani, Assignment 1")
plt.legend(loc='upper left')
plt.show()
plt.savefig("plot.png")